package com.itheima.leetcode.od.b.graph;

import java.util.Arrays;

/**
 * (C卷,200分)- 路口最短时间问题（Java & JS & Python & C）
 * <p>
 * 题目描述
 * <p>
 * 假定街道是棋盘型的，每格距离相等，车辆通过每格街道需要时间均为 timePerRoad；
 * <p>
 * 街道的街口（交叉点）有交通灯，灯的周期 T（=lights[row][col]）各不相同；
 * <p>
 * 车辆可直行、左转和右转，其中直行和左转需要等相应 T 时间的交通灯才可通行，右转无需等待。
 * <p>
 * 现给出 n * m 个街口的交通灯周期，以及起止街口的坐标，计算车辆经过两个街口的最短时间。
 * <p>
 * 其中：
 * <p>
 * 起点和终点的交通灯不计入时间，且可以在任意方向经过街口
 * 不可超出 n * m 个街口，不可跳跃，但边线也是道路（即：lights[0][0] -> lights[0][1] 是有效路径）
 * <p>
 * 输入描述
 * <p>
 * 第一行输入 n 和 m，以空格分隔
 * <p>
 * 之后 n 行输入 lights矩阵，矩阵每行m个整数，以空格分隔
 * <p>
 * 之后一行输入 timePerRoad
 * <p>
 * 之后一行输入 rowStart colStart，以空格分隔
 * <p>
 * 最后一行输入 rowEnd colEnd，以空格分隔
 * <p>
 * 输出描述
 * <p>
 * lights[rowStart][colStart] 与 lights[rowEnd][colEnd] 两个街口之间的最短通行时间
 * <p>
 * 用例
 * <p>
 * 输入	3 3
 * <p>
 * 1 2 3
 * <p>
 * 4 5 6
 * <p>
 * 7 8 9
 * <p>
 * 60
 * <p>
 * 0 0
 * <p>
 * 2 2
 * <p>
 * 输出	245
 * 说明	行走路线为 (0,0) -> (0,1) -> (1,1) -> (1,2) -> (2,2) 走了4格路，2个右转，1个左转，共耗时 60+0+60+5+60+0+60=245
 */
public class DFSShortestTimeOfIntersections {
    public static void main(String[] args) {
        /*Scanner sc = new Scanner(System.in);

        n = sc.nextInt();
        m = sc.nextInt();

        lights = new int[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                lights[i][j] = sc.nextInt();
            }
        }

        timePreRoad = sc.nextInt();

        rowStart = sc.nextInt();
        colStart = sc.nextInt();

        rowEnd = sc.nextInt();
        colEnd = sc.nextInt();*/

        int n = 3;
        int m = 3;

        int[][] lights = Arrays.stream("1 2 3\n4 5 6\n7 8 9".split("\n"))
                .map(s -> Arrays.stream(s.split(" "))
                        .mapToInt(Integer::parseInt)
                        .toArray())
                .toArray(int[][]::new);

        int timePreRoad = 60;

        int rowStart = 0;
        int colStart = 0;

        int rowEnd = 2;
        int colEnd = 2;

        System.out.println(getResult(n, m, lights, timePreRoad, rowStart, colStart, rowEnd, colEnd));
    }

    static int[][] offsets = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

    public static int getResult(int n, int m, int[][] lights, int timePreRoad, int rowStart, int colStart, int rowEnd,
                                int colEnd) {
        // 记录访问过的点，防止走回路
        boolean[][] visited = new boolean[n][m];
        // 初始时起点位置标记为访问过
        visited[rowStart][colStart] = true;

        // 记录起点到终点的最小花费时间，这里minCost定义为数组，是为了其在dfs函数调用结束后，不会被释放内存，因为它是引用类型变量
        int[] minCost = {Integer.MAX_VALUE};
        // 开始暴搜所有起点到终点的路径
        dfs(rowStart, colStart, -1, -1, 0, minCost, rowEnd, colEnd, timePreRoad, lights, visited);
        return minCost[0];
    }

    /**
     * 暴力搜索
     *
     * @param curX        当前位置横坐标
     * @param curY        当前位置纵坐标
     * @param preX        上一个位置横坐标
     * @param preY        上一个位置纵坐标
     * @param cost        到达当前位置花费的时间
     * @param minCost     记录起点到终点的最小花费时间
     * @param rowEnd
     * @param colEnd
     * @param timePreRoad
     * @param lights
     * @param visited
     */
    public static void dfs(int curX, int curY, int preX, int preY, int cost, int[] minCost, int rowEnd, int colEnd,
                           int timePreRoad, int[][] lights, boolean[][] visited) {
        // 如果到达当前前花费的时间cost 达到了 已知minCost，那么后续路径就没必要探索了，因为必然要比minCost大
        if (cost >= minCost[0]) {
            return;
        }

        // 如果当前点是终点，且花费的时间cost更少，则更新minCost
        if (curX == rowEnd && curY == colEnd) {
            minCost[0] = cost;
            return;
        }

        // 否则，从当前位置的四个方向继续探索路径
        for (int[] offset : offsets) {
            // 新位置
            int nextX = curX + offset[0];
            int nextY = curY + offset[1];

            // 新位置越界或者已经访问过，则不能访问，继续其他方向探索
            if (nextX < 0 || nextX >= lights.length || nextY < 0 || nextY >= lights[0].length
                    || visited[nextX][nextY]) {
                continue;
            }

            // 标记新位置访问过
            visited[nextX][nextY] = true;

            // 根据pre,cur,next三点，判断拐弯方向
            int direction = getDirection(preX, preY, curX, curY, nextX, nextY);

            // cur到达next位置必须要增加timePreRoad个时间
            int increment = timePreRoad;
            // preX=-1, preY=-1 表示pre位置不存在，此时探索下一个位置不需要花费等待周期
            if (preX >= 0 && preY >= 0 && direction >= 0) {
                // pre位置存在，且cur->next是左拐或者直行，则需要增加当前位置对应的等待周期时间
                increment += lights[curX][curY];
            }

            // 递归进入新位置
            dfs(nextX, nextY, curX, curY, cost + increment, minCost, rowEnd, colEnd, timePreRoad, lights, visited);

            // 回溯
            visited[nextX][nextY] = false;
        }
    }

    /**
     * 根据三点坐标，确定拐弯方向
     *
     * @param preX  前一个点横坐标
     * @param preY  前一个点纵坐标
     * @param curX  当前点横坐标
     * @param curY  当前点纵坐标
     * @param nextX 下一个点横坐标
     * @param nextY 下一个点纵坐标
     * @return cur到next的拐弯方向， >0 表示向左拐， ==0 表示直行（含调头）， <0 表示向右拐
     */
    public static int getDirection(int preX, int preY, int curX, int curY, int nextX, int nextY) {
        // 向量 pre->cur
        int dx1 = curX - preX;
        int dy1 = curY - preY;

        // 向量 cur->next
        int dx2 = nextX - curX;
        int dy2 = nextY - curY;

        // 两个向量的叉积 >0 表示向左拐， ==0 表示直行（含调头）， <0 表示向右拐
        return dx1 * dy2 - dx2 * dy1;
    }
}